package DynamicProgramming;


import java.util.Arrays;

/**
 * 给一个正整数 n, 找到若干个完全平方数(比如1, 4, 9, ... )使得他们的和等于 n。你需要让平方数的个数最少。
 * 样例
 *
 * 给出 n = 12, 返回 3 因为 12 = 4 + 4 + 4。
 * 给出 n = 13, 返回 2 因为 13 = 4 + 9。
 *
 * */
public class 最少平方和的数量 {

    public static int numSquares(int n) {
        int k = (int)Math.sqrt(n); //当前值的开方，超过这个值的平方肯定大于n
        //dp[i] 表示i最少可由 dp[i] 个平方数组成
        int[] dp = new int[n+1];
        int[] pow = new int[k+1];  //记录
        //pow数组记录了 0-k的完全平方数值  k^2 <= n
        for(int i=1;i<k+1;i++){
            pow[i]=i*i;
        }

        //初始化，每个数n 都可以由 n个1组成，因此初始化为本身
        for(int i=1;i<n+1;i++){
            dp[i]=i;
        }
        //从n==2开始求最少，
        for(int i=2;i<n+1;i++){
            for(int j=2;j<k+1;j++){
                //当前平方的值小于等于要组成的i值时才判断
                if(pow[j]<=i) {
                    int index= i / pow[j]; //首先看可以由几个当前平方数组成
                    //在减去index倍的当前平方数 时的dp值+index取最小的
                    /**
                     * 比如， n=16 k=4 那么 pow数组为[0,1,4,9,16]
                     * 当 i=15 时，从j=2 也就是值4开始遍历  index = 15/4 = 3 ,说明当前值可由3个4组成
                     * 然后剩下的 去之前的最少查，  dp[i- index * pow[j]] + index  取最小的即当前的最小值
                     * */
                    dp[i]=Math.min(dp[i], dp[i-index* pow[j]] + index);
                }
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(numSquares(9));
    }
}
